package com.sicheng.蓝桥.国赛准备.第10届CPP;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/20 15:22
 */
public class E路径计数 {
    /**
     * E-路径计数：
     * 有一个7X7的方格。方格左上角顶点坐标为(0,0)，右下角坐标为(7,7)。
     * 求满足下列条件的路径条数：
     * 1、起点和终点都是(0,0)
     * 2、路径不自交
     * 3、路径长度不大于12
     * 4、对于每一个顶点，有上下左右四个方向可以走，但是不能越界。
     */

    //方向向量
    static int[][] d = {
            {1, 0},
            {0, 1},
            {-1, 0},
            {0, -1}
    };

    static int n = 7;
    static int[][] g = new int[n + 1][n + 1];
    static int count;
    static int limit = 12;

    public static void main(String[] args) {
        dfs(0, 0);
        //从开始点出发往右再往左这种路径是会被考虑在内的，但是不符合题意（重合肯定相交了），
        //同理向下再向上也是如此，所以最终答案-2即可,这里非常容易忽略-2,在下debug一下午都没发现这个重合情况
        System.out.println(count - 2);
    }

    private static void dfs(int i, int j) {
        if (j == 0 && i == 0 && g[i][j] > 0) {
            count++;
            return;
        }

        for (int[] direction : d) {

            // (i,j) --> (x,y)
            int x = i + direction[0];
            int y = j + direction[1];
            if (x >= 0 && x <= n && y >= 0 && y <= n && g[x][y] == 0 && g[i][j] < limit) {

                g[x][y] = g[i][j] + 1;
                dfs(x, y);
                g[x][y] = 0;
            }
        }
    }
}
